SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Architecture Dataflow</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Architecture Dataflow</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="fr" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><p>Le <i><b><span class="lang-en" lang="en">dataflow</span></b></i> (en <a href="Fran%C3%A7ais" title="Français">français</a> : <span class="lang-fr" lang="fr">flux de données</span>) est une architecture où les données sont des entités actives qui traversent le programme de manière <a href="Asynchrone" class="mw-redirect" title="Asynchrone">asynchrone</a>, contrairement à l'architecture classique <a href="Architecture_de_von_Neumann" title="Architecture de von Neumann">von Neumann</a>, où elles attendent passivement en <a href="M%C3%A9moire_informatique" class="mw-redirect" title="Mémoire informatique">mémoire</a> pendant que le programme est exécuté séquentiellement suivant le contenu du <a href="Registre_(informatique)" class="mw-redirect" title="Registre (informatique)">pointeur de programme</a> (PC). On parle aussi d'ordinateur cadencé par les données.

</p>

<div class="mw-heading mw-heading2"><h2 id="Principe_de_fonctionnement">Principe de fonctionnement</h2></div>

<p>Dans une architecture flux de données, les <a href="Programmes" class="mw-redirect" title="Programmes">programmes</a> sont représentés sous forme de <a href="Graphe_(th%C3%A9orie_des_graphes)" class="mw-redirect" title="Graphe (théorie des graphes)">graphes</a> : un <a href="N%C5%93ud_(r%C3%A9seau)" title="Nœud (réseau)">nœud</a> représente une opération à effectuer, tandis que les données circulent sur les <a href="Lexique_de_la_th%C3%A9orie_des_graphes#A" class="mw-redirect" title="Lexique de la théorie des graphes">arcs</a> et forment les entrées aux nœuds. Les données sont transportées par des jetons (<i><span class="lang-en" lang="en">tokens</span></i>). La règle de base, dite « de déclenchement », instaure que lorsqu'un nœud voit toutes ses entrées satisfaites, il est activé et produit une valeur en sortie, et les jetons présents en entrée sont supprimés.

</p><p>Ces architectures sont étroitement couplées aux langages de <a href="Programmation_fonctionnelle" title="Programmation fonctionnelle">programmation fonctionnelle</a>. Elles ne génèrent pas d'<a href="Effet_de_bord_(informatique)" title="Effet de bord (informatique)">effet de bord</a>, donc ne nécessitent pas de <a href="M%C3%A9moire_partag%C3%A9e_(communication_inter-processus)" title="Mémoire partagée (communication inter-processus)">mémoire partagée</a>, ni de <a href="Unit%C3%A9_de_contr%C3%B4le" title="Unité de contrôle">séquenceur</a> ou de <a href="Registre_(informatique)" class="mw-redirect" title="Registre (informatique)">pointeur de programme</a>. Elles sont aussi éminemment parallèles : l'unité responsable de l'exécution des instructions issue de la mémoire contenant le programme doit posséder un nombre relativement élevé de processeurs (16 et plus) afin de maximiser la puissance totale de l'ordinateur.

</p><p>Plusieurs unités de calcul traitant des données différentes les classent dans la famille des ordinateurs <a href="MIMD" class="mw-redirect" title="MIMD">MIMD</a> (<span class="lang-en" lang="en">Multiple Instructions, Multiple Data</span>).

</p>

<div class="mw-heading mw-heading2"><h2 id="Les_graphes_comme_langage">Les graphes comme langage</h2></div>

<p>Un nœud computationnel peut être représenté comme le sommet d'un <a href="Graphe_(th%C3%A9orie_des_graphes)" class="mw-redirect" title="Graphe (théorie des graphes)">graphe</a>. Les jetons circulent sur les arcs reliant les sommets. Quand deux jetons contenant respectivement les <span class="nowrap">valeurs 3 et 5</span> se présentent aux entrées du nœud, celui-ci exécute l'opération pour laquelle il est conçu (ici une addition), génère un jeton en sortie représentant la somme (<span class="nowrap">3 + 5</span>), 8, et supprime les jetons d'entrée :

</p>

/* start https://fr.wikipedia.org/ */

@media all and (max-width:720px){.mw-parser-output .tmulti>.thumbinner{width:100%!important;max-width:none!important}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:none!important;width:100%!important;text-align:center}}

/* end https://fr.wikipedia.org/ */

</style><div class="thumb tmulti tnone center"><div class="thumbinner" style="width:408px;max-width:408px"><div class="tsingle" style="float:left;margin:1px;width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption" style="clear:left">Un nœud de base d'une architecture <i><span class="lang-en" lang="en">dataflow</span></i>.</div></div><div class="tsingle" style="float:left;margin:1px;width:202px;max-width:202px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption" style="clear:left">Activation d'un nœud. Notez la disparition des jetons d'entrée après la production d'une valeur en sortie.</div></div><div style="clear:left"></div></div></div>

<p>L'expression plus complexe z = (x + y) × (x - y) correspond au graphe ci-dessous. On constate que le parallélisme est implicite : les deux nœuds <b>+</b> et <b>-</b> sont activables simultanément.

</p>

<p>Grâce à deux types de nœuds appelés <i><span class="lang-en" lang="en">switch</span></i> et <i><span class="lang-en" lang="en">merge</span></i>, on peut coder la condition <i>si</i>. Le premier type possède deux entrées et deux sorties, tandis que le second possède trois entrées et une sortie. Le type <i><span class="lang-en" lang="en">switch</span></i> répercutera son jeton d'entrée sur l'une ou l'autre de ses sorties suivant l'état de sa seconde entrée. Le type <i><span class="lang-en" lang="en">merge</span></i> fera la sélection d'un de ses deux jetons d'entrée suivant la valeur d'un troisième. Schématiquement :

</p>

<table>

</td>

</td></tr></tbody></table>

<p>Voici deux exemples de ces instructions, dans un test conditionnel et dans une boucle. Notez l'initialisation à Faux sur le nœud <i><span class="lang-en" lang="en">merge</span></i> pour correctement sélectionner la valeur de x.

</p>

<table>

</td>

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Implications_de_l'utilisation_de_graphes"><span id="Implications_de_l.27utilisation_de_graphes"></span>Implications de l'utilisation de graphes</h3></div>

<ol><li>Localité : les interdépendances entre les données sont très localisées, contrairement aux langages impératifs habituels qui utilisent des <a href="Variable_globale" title="Variable globale">variables globales</a> (situées « loin » des procédures qui sont susceptibles de les modifier).</li>

<li>Pas d'effets de bord, pas de notion de passage de paramètres par référence : les valeurs sont dupliquées.</li>

<li>Dépliage des boucles : pour paralléliser l'exécution des boucles, le code doit être déplié pour que chaque <a href="It%C3%A9ration" title="Itération">itération</a> puisse être exécutées en parallèle.</li>

<li>Règle de la référence unique :</li></ol>

<dl><dd><dl><dd>le nom d'une variable ne peut apparaître qu'une seule fois dans une assignation. Pour éviter cela, on renomme la variable à partir de ce point, et on utilise ce nouveau nom par la suite. Par exemple :</dd></dl></dd></dl>

<p><br>

</p>

<td>X = P - Q

</td></tr>

<tr>

<td><b>X1</b> = X × Y

</td></tr>

<tr>

<td>W = <b>X1</b> - Y

</td></tr></tbody></table>

<dl><dd><dl><dd>Cette règle a été proposée en 1968.</dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Structure_des_graphes">Structure des graphes</h2></div>

<p>Pour mieux comprendre comment les programmes flot de données peuvent être exécutés par un ordinateur, il est plus aisé de représenter les graphes sous la forme d'une collection de structures reliées entre elles par des pointeurs.

</p><p>Le premier graphe z = (x + y) × (x - y) peut être représenté par cette structure :

</p>

<p>Chaque nœud est représenté par un bloc dont le premier élément est l'opération à effectuer, puis suivent les emplacements indiqués par des parenthèses « [ ] » qui sont destinées à contenir les paramètres de l'opération, ainsi que des emplacements contenant les adresses où sera placé le résultat. Certains emplacements peuvent éventuellement contenir des constantes.

</p><p>Les itérations ne posent pas de problème non plus, ci-dessous la structure de la <a href="Boucle_while" title="Boucle while">boucle WHILE</a> précédemment évoquée :

</p>

<div class="mw-heading mw-heading2"><h2 id="Types_de_machine">Types de machine</h2></div>

<p>Il existe plusieurs types d'ordinateur flot de données, mais on peut distinguer deux modèles :

</p>

<ul><li>Le modèle statique : il n'y a qu'un seul jeton sur un arc à un instant donné ;</li>

<li>Le modèle dynamique : il peut y avoir plusieurs jetons en attente sur un arc.</li></ul>

<p>Des machines hybrides <i><span class="lang-en" lang="en">dataflow</span></i>/<a href="Architecture_de_von_Neumann" title="Architecture de von Neumann">von Neumann</a> ont aussi été conçues (<a href="Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">MIT</a> P-RISC).

</p>

<div class="mw-heading mw-heading3"><h3 id="Machines_statiques">Machines statiques</h3></div>

<p>Rentrent dans cette catégorie la machine conçue par <a href="Jack_Dennis" title="Jack Dennis">Jack Dennis</a> du <a href="Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">Massachusetts Institute of Technology</a> en <a href="1974" title="1974">1974</a>. La difficulté rencontrée sur cette architecture est la contrainte de n'avoir qu'une seule valeur (jeton) sur un arc à un moment donné (car on ne peut pas faire de différence entre les jetons). Elle est effacée par l'utilisation de jetons de contrôles qui acquiescent la transmission des données d'un nœud à un autre.

</p>

<div class="mw-heading mw-heading3"><h3 id="Machines_dynamiques">Machines dynamiques</h3></div>

<p>Ces machines associent un marqueur (<i><span class="lang-en" lang="en">tag</span></i>), ou une couleur, à chaque jeton. La règle de base est modifiée, et devient : « lorsqu'un nœud voit toutes ses entrées satisfaites par des jetons de même couleur, il est activé et produit une valeur en sortie, avec sa propre couleur, et les marqueurs et jetons d'entrées sont effacés ». L'architecture en est simplifiée et le dépliage des boucles se fait tout seul : il est créé autant de couleurs et jetons que nécessaire.

</p>

<div class="mw-heading mw-heading3"><h3 id="Exemple_:_la_machine_dataflow_dynamique_de_Manchester">Exemple : la machine <i><span class="lang-en" lang="en">dataflow</span></i> dynamique de Manchester</h3></div>

<p>Son architecture simplifiée est représentée par la figure ci à droite. Elle est volontairement simplifiée, mais est tout à fait représentative des machines de type dynamique. On remarque immédiatement qu'elle est très facilement « <a href="Pipeline_(informatique)" class="mw-redirect" title="Pipeline (informatique)">pipelinable</a> », ce qui bien sûr améliore sensiblement les performances. Il est spécifié en caractères italiques le type de paquets circulant entre deux unités.

</p><p>Les jetons appartenant à une même instruction sont appairés dans l'unité de correspondance. Ils sont envoyés vers l'unité où sont stockées les instructions, d'où ils chargent les instructions dont ils dépendent. Ces paquets enfin exécutables sont dirigés vers l'unité de calcul qui, à la suite de l'exécution de l'instruction reçue en entrée, va émettre de nouveaux jetons. L'unité d'entrée/sortie sert à communiquer avec l'ordinateur externe qui contrôle la machine <i><span class="lang-en" lang="en">dataflow</span></i>, par le biais du bus schématisé verticalement, qui permet l'injection de paquets ou bien leur récupération. La file d'attente « jetons » est simplement une mémoire tampon <a href="First_in%2C_first_out" class="mw-redirect" title="First in, first out">FIFO</a>.

</p><p>Les jetons sont formés de :

</p>

<ul><li>37 <abbr class="abbr" title="bits"><a href="Bit_(informatique)" class="mw-redirect" title="Bit (informatique)">bits</a></abbr> de données, associées à</li>

<li>un marqueur de 36 <abbr class="abbr" title="bits"><a href="Bit_(informatique)" class="mw-redirect" title="Bit (informatique)">bits</a></abbr> suivi de</li>

<li>une adresse de destination sur 22 <abbr class="abbr" title="bits"><a href="Bit_(informatique)" class="mw-redirect" title="Bit (informatique)">bits</a></abbr>, puis</li>

<li>un second marqueur de 1 <abbr class="abbr" title="bit"><a href="Bit_(informatique)" class="mw-redirect" title="Bit (informatique)">bit</a></abbr>.</li></ul>

<p>Étant donné que de larges itérations ou de vastes ensembles de données peuvent provoquer un dépassement de capacité (en nombre de jetons), une unité particulière est couplée à l'unité de correspondance pour pallier ce cas. L'unité de calcul va bien sûr contenir plusieurs <a href="Unit%C3%A9_arithm%C3%A9tique_et_logique" title="Unité arithmétique et logique">unités arithmétiques et logiques</a> pour permettre d'exécuter les instructions en parallèle.

</p>

<div class="mw-heading mw-heading2"><h2 id="Langages">Langages</h2></div>

<ul><li><b>Id</b> a été mis au point à Irvine (Université de <a href="Californie" title="Californie">Californie</a>), puis au <a href="Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">MIT</a></li>

<li><b>SISAL</b> (<i><span class="lang-en" lang="en">Streams and Iteration in a Single Assignment Language</span></i>) à l'université de <a href="Manchester" title="Manchester">Manchester</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Historique">Historique</h2></div>

<p>Les premières idées et concepts qui ont donné naissance à ces architectures sont nés dans les années <a href="1960" title="1960">1960</a>.

</p><p>Les premiers <a href="Ordinateur" title="Ordinateur">ordinateurs</a> de ce type sont nés au début des <span class="nowrap"><a href="Ann%C3%A9es_1970" title="Années 1970">années 1970</a></span>, d'abord aux <a href="%C3%89tats-Unis" title="États-Unis">États-Unis</a> et au <a href="Japon" title="Japon">Japon</a>, mais aussi en <a href="France" title="France">France</a> avec le LAU (Langage à Assignation Unique, CERT-ONERA de <a href="Toulouse" title="Toulouse">Toulouse</a>). Les constructeurs qui se sont impliqués sont : <a href="Texas_Instruments" title="Texas Instruments">Texas Instruments</a>, <a href="NEC" title="NEC">NEC</a>, OKI etc. Certaines machines ont été construites sur la base de microprocesseurs tel que le <a href="Zilog" title="Zilog">Zilog</a> Z8001 et <a href="Motorola" title="Motorola">Motorola</a> 88110 ou bien encore des microprocesseurs en tranches <a href="Advanced_Micro_Devices" title="Advanced Micro Devices">AMD</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Quelques_machines">Quelques machines</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Machines_à_architecture_statique"><span id="Machines_.C3.A0_architecture_statique"></span>Machines à architecture statique</h3></div>

<ul><li>MIT <span class="lang-en" lang="en">Static Dataflow Architecture</span>, un prototype avec 8 processeurs.</li>

<li>HDFM, <span class="lang-en" lang="en">Hughes Dataflow Multiprocessor</span>, avec 512 processeurs.</li>

<li>LAU, <span class="lang-en" lang="en">TI's Distributed Data Processor</span>, DDM1, etc.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Machines_a_jetons_marqués_(architecture_dynamique)"><span id="Machines_a_jetons_marqu.C3.A9s_.28architecture_dynamique.29"></span>Machines a jetons marqués (architecture dynamique)</h3></div>

<ul><li>MIT <span class="lang-en" lang="en">Tagged-Token Dataflow Machine</span>, 4 processeurs par <i><span class="lang-en" lang="en">cluster</span></i>, les clusters sont interconnectés sur un réseau en boucle.</li>

<li><span class="nowrap">SIGMA-1</span>, <a href="Superordinateur" title="Superordinateur">superordinateur</a> <a href="Japon" title="Japon">Japonais</a>, 128 processeurs, 1988.</li>

<li><a href="LDF_100" title="LDF 100">LFD 100</a>, entre 5 et 128 processeurs, 1986.</li>

<li>PATTSY, <span class="lang-en" lang="en">Processor Array Tagged-Token System</span>, système expérimental australien. 18 processeurs <span class="nowrap">Intel 8085</span> reliés à un <span class="nowrap">IBM-PC</span>.</li>

<li>DDDP, <span class="lang-en" lang="en">Distributed Data Driven Processor</span>, conception Japonaise, 16 processeurs.</li>

<li><span class="nowrap">Q-p</span>, SDFA, CSIRAC II, <span class="nowrap">PIM-D</span> etc.</li></ul>

<p>Il est tout à fait possible que le <i><span class="lang-en" lang="en">dataflow</span></i> soit utilisé sous une forme « moderne » pour équiper un <a href="Superordinateur" title="Superordinateur">superordinateur</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Références"><span id="R.C3.A9f.C3.A9rences"></span>Références</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Liens_internes">Liens internes</h3></div>

<ul><li><a href="Programmation_fonctionnelle" title="Programmation fonctionnelle">Programmation fonctionnelle</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Liens_externes">Liens externes</h3></div>

<ul><li><abbr class="abbr indicateur-format format-pdf" title="Document au format Portable Document Format (PDF)">[PDF]</abbr> <a rel="nofollow" class="external text" href="http://www.cs.wisc.edu/~isca2005/ttda.pdf">Executing a Program on the MIT Tagged-Token Dataflow Architecture</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www.jpaulmorrison.com/fbp/index.shtml">Flow-based Programming</a> : un livre sur la programmation orientée flot de données.</li></ul>

<ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer" typeof="mw:File"></span></span> <span class="bandeau-portail-texte">Portail de l’informatique</span> </span></li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2025-03-04" href="https://fr.wikipedia.org/wiki/?title=Architecture_Dataflow&oldid=223572149">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>